Search Results

Documents authored by Schmid, Ulrich

Document
DOI: 10.4230/DagRep.13.7.34
Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)

Authors: Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid

Published in: Dagstuhl Reports, Volume 13, Issue 7 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23272 "Epistemic and Topological Reasoning in Distributed Systems." The seminar brought together experts in combinatorial topology and epistemic logic interested in distributed systems, with the aim of exploring the directions that the recent interaction between those approaches can take, identifying challenges and opportunities.
Cite as

Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid. Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272). In Dagstuhl Reports, Volume 13, Issue 7, pp. 34-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{castaneda_et_al:DagRep.13.7.34,
  author =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  title =	{{Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)}},
  pages =	{34--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{7},
  editor =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.7.34},
  URN =		{urn:nbn:de:0030-drops-197742},
  doi =		{10.4230/DagRep.13.7.34},
  annote =	{Keywords: combinatorial topology, distributed systems, epistemic logic, multi-agent systems, interpreted systems, dynamic epistemic logic, simplicial semantics, knowledge-based approach, distributed computing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.100
The Time Complexity of Consensus Under Oblivious Message Adversaries

Authors: Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study the problem of solving consensus in synchronous directed dynamic networks, in which communication is controlled by an oblivious message adversary that picks the communication graph to be used in a round from a fixed set of graphs 𝐃 arbitrarily. In this fundamental model, determining consensus solvability and designing efficient consensus algorithms is surprisingly difficult. Enabled by a decision procedure that is derived from a well-established previous consensus solvability characterization for a given set 𝐃, we study, for the first time, the time complexity of solving consensus in this model: We provide both upper and lower bounds for this time complexity, and also relate it to the number of iterations required by the decision procedure. Among other results, we find that reaching consensus under an oblivious message adversary can take exponentially longer than both deciding consensus solvability and broadcasting the input value of some unknown process to all other processes.
Cite as

Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid. The Time Complexity of Consensus Under Oblivious Message Adversaries. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 100:1-100:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{winkler_et_al:LIPIcs.ITCS.2023.100,
  author =	{Winkler, Kyrill and Paz, Ami and Rincon Galeana, Hugo and Schmid, Stefan and Schmid, Ulrich},
  title =	{{The Time Complexity of Consensus Under Oblivious Message Adversaries}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{100:1--100:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.100},
  URN =		{urn:nbn:de:0030-drops-176030},
  doi =		{10.4230/LIPIcs.ITCS.2023.100},
  annote =	{Keywords: dynamic networks, oblivious message adversaries, consensus, time complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.73
Continuous Tasks and the Asynchronous Computability Theorem

Authors: Hugo Rincon Galeana, Sergio Rajsbaum, and Ulrich Schmid

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The celebrated 1999 Asynchronous Computability Theorem (ACT) of Herlihy and Shavit characterized distributed tasks that are wait-free solvable and uncovered deep connections with combinatorial topology. We provide an alternative characterization of those tasks by means of the novel concept of continuous tasks, which have an input/output specification that is a continuous function between the geometric realizations of the input and output complex: We state and prove a precise characterization theorem (CACT) for wait-free solvable tasks in terms of continuous tasks. Its proof utilizes a novel chromatic version of a foundational result in algebraic topology, the simplicial approximation theorem, which is also proved in this paper. Apart from the alternative proof of the ACT implied by our CACT, we also demonstrate that continuous tasks have an expressive power that goes beyond classic task specifications, and hence open up a promising venue for future research: For the well-known approximate agreement task, we show that one can easily encode the desired proportion of the occurrence of specific outputs, namely, exact agreement, in the continuous task specification.
Cite as

Hugo Rincon Galeana, Sergio Rajsbaum, and Ulrich Schmid. Continuous Tasks and the Asynchronous Computability Theorem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 73:1-73:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{galeana_et_al:LIPIcs.ITCS.2022.73,
  author =	{Galeana, Hugo Rincon and Rajsbaum, Sergio and Schmid, Ulrich},
  title =	{{Continuous Tasks and the Asynchronous Computability Theorem}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{73:1--73:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.73},
  URN =		{urn:nbn:de:0030-drops-156696},
  doi =		{10.4230/LIPIcs.ITCS.2022.73},
  annote =	{Keywords: Wait-free computability, topology, distributed computing, decision tasks, shared memory}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.17
A Characterization of Consensus Solvability for Closed Message Adversaries

Authors: Kyrill Winkler, Ulrich Schmid, and Yoram Moses

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Distributed computations in a synchronous system prone to message loss can be modeled as a game between a (deterministic) distributed algorithm versus an omniscient message adversary. The latter determines, for each round, the directed communication graph that specifies which messages can reach their destination. Message adversary definitions range from oblivious ones, which pick the communication graphs arbitrarily from a given set of candidate graphs, to general message adversaries, which are specified by the set of sequences of communication graphs (called admissible communication patterns) that they may generate. This paper provides a complete characterization of consensus solvability for closed message adversaries, where every inadmissible communication pattern has a finite prefix that makes all (infinite) extensions of this prefix inadmissible. Whereas every oblivious message adversary is closed, there are also closed message adversaries that are not oblivious. We provide a tight non-topological, purely combinatorial characterization theorem, which reduces consensus solvability to a simple condition on prefixes of the communication patterns. Our result not only non-trivially generalizes the known combinatorial characterization of the consensus solvability for oblivious message adversaries by Coulouma, Godard, and Peters (Theor. Comput. Sci., 2015), but also provides the first combinatorial characterization for this important class of message adversaries that is formulated directly on the prefixes of the communication patterns.
Cite as

Kyrill Winkler, Ulrich Schmid, and Yoram Moses. A Characterization of Consensus Solvability for Closed Message Adversaries. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{winkler_et_al:LIPIcs.OPODIS.2019.17,
  author =	{Winkler, Kyrill and Schmid, Ulrich and Moses, Yoram},
  title =	{{A Characterization of Consensus Solvability for Closed Message Adversaries}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.17},
  URN =		{urn:nbn:de:0030-drops-118038},
  doi =		{10.4230/LIPIcs.OPODIS.2019.17},
  annote =	{Keywords: Dynamic networks, Consensus, Message Adversary}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.DISC.2018
LIPIcs, Volume 121, DISC'18, Complete Volume

Authors: Ulrich Schmid and Josef Widder

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
LIPIcs, Volume 121, DISC'18, Complete Volume
Cite as

32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{schmid_et_al:LIPIcs.DISC.2018,
  title =	{{LIPIcs, Volume 121, DISC'18, Complete Volume}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018},
  URN =		{urn:nbn:de:0030-drops-98456},
  doi =		{10.4230/LIPIcs.DISC.2018},
  annote =	{Keywords: Software and its engineering, Distributed systems organizing principles, Computing methodologies, Distributed computing methodologies}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.DISC.2018.0
Front Matter, Table of Contents, Preface, Conference Organization, Awards

Authors: Ulrich Schmid and Josef Widder

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization, Awards
Cite as

32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{schmid_et_al:LIPIcs.DISC.2018.0,
  author =	{Schmid, Ulrich and Widder, Josef},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization, Awards}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.0},
  URN =		{urn:nbn:de:0030-drops-97899},
  doi =		{10.4230/LIPIcs.DISC.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization, Awards}
}
Document
DOI: 10.4230/DagSemProc.08371.1
08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips

Authors: Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract
From September the $7^{\text{th}}$, 2008 to September the $10^{\text{th}}$, 2008 the Dagstuhl Seminar 08371 ``Fault-Tolerant Distributed Algorithms on VLSI Chips '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. The seminar was devoted to exploring whether the wealth of existing fault-tolerant distributed algorithms research can be utilized for meeting the challenges of future-generation VLSI chips. During the seminar, several participants from both the VLSI and distributed algorithms' discipline, presented their current research, and ongoing work and possibilities for collaboration were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid. 08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:DagSemProc.08371.1,
  author =	{Charron-Bost, Bernadette and Dolev, Shlomi and Ebergen, Jo and Schmid, Ulrich},
  title =	{{08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips }},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.1},
  URN =		{urn:nbn:de:0030-drops-19283},
  doi =		{10.4230/DagSemProc.08371.1},
  annote =	{Keywords: Fault-tolerant distributed algorithms, fault tolerance, VLSI systems-on-chip, synchronous vs.\backslash asynchronous circuits, digital logic, specifications}
}
Document
DOI: 10.4230/DagSemProc.08371.2
08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips

Authors: Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract
Chips was devoted to exploring whether the wealth of existing fault-tolerant distributed algorithms research can be utilized for meeting the challenges of future-generation VLSI chips. Participants from both the distributed fault-tolerant algorithms community, interested in this emerging application domain, and from the VLSI systems-on-chip and digital design community, interested in well-founded system-level approaches to fault-tolerance, surveyed the current state-of-the-art and tried to identify possibilities to work together. The seminar clearly achieved its purpose: It became apparent that most existing research in Distributed Algorithms is too heavy-weight for being immediately applied in the “core” VLSI design context, where power, area etc. are scarce resources. At the same time, however, it was recognized that emerging trends like large multicore chips and increasingly critical applications create new and promising application domains for fault-tolerant distributed algorithms. We are convinced that the very fruitful cross-community interactions that took place during the Dagstuhl seminar will contribute to new research activities in those areas.
Cite as

Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid. 08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:DagSemProc.08371.2,
  author =	{Charron-Bost, Bernadette and Dolev, Shlomi and Ebergen, Jo and Schmid, Ulrich},
  title =	{{08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips }},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.2},
  URN =		{urn:nbn:de:0030-drops-19270},
  doi =		{10.4230/DagSemProc.08371.2},
  annote =	{Keywords: Fault-tolerant distributed algorithms, fault tolerance, VLSI systemson- chip, synchronous vs. asynchronous circuits, digital logic, specifications}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact